package dp.备忘录dfs;

import java.util.Arrays;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 零钱兑换ii518.java
 * @createTime 2024年05月09日 15:35:00
 */
public class 零钱兑换ii518 {

	//表示金额为i的时候，剩余价格为j的时候的可选的方案数量
	private int[][] dp;

	public int change(int amount, int[] coins) {
		dp = new int[coins.length][amount + 1];
		for (int[] arr : dp) {
			Arrays.fill(arr, -1);
		}
		return backTrace(coins, 0, amount);
	}

	public int backTrace(int[] coins, int coinIndex, int amount) {
		//如果金额到0了，就结束
		if (amount < 0) {
			return 0;
		}
		if (coinIndex == coins.length) {
			return amount == 0 ? 1 : 0;
		}
		//这个金额的已经存在过
		if (dp[coinIndex][amount] != -1) {
			return dp[coinIndex][amount];
		}
		//选择用
		int choose = backTrace(coins, coinIndex, amount - coins[coinIndex]);
		int noChoose = backTrace(coins, coinIndex + 1, amount);
		dp[coinIndex][amount] = choose + noChoose;
		return dp[coinIndex][amount];
	}
}
